import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PrimosParaleloSobDemanda extends Thread {
	private static Queue<Intervalo> intervalos = new LinkedList<Intervalo>();
	
	private List<Integer> listaDePrimos;
	private int numero;

	private PrimosParaleloSobDemanda(int numero) {
		this.listaDePrimos = new ArrayList<Integer>();
		this.numero = numero;
	}

	public void run() {
		while (true) {
			Intervalo intervalo = null;
			synchronized (intervalos) {
				if (intervalos.isEmpty()) {
					break;
				}
				intervalo = intervalos.poll();
			}
			
			long antes = System.nanoTime();
			List<Integer> primosIntervalo = PrimosSequencial.buscaPrimos(
					intervalo.getInicio(), intervalo.getFim());
			listaDePrimos.addAll(primosIntervalo);
			long depois = System.nanoTime();
			long tempoEmNs = depois - antes;
			System.out.println("Thread " + numero
					+ " trabalhou com o intervalo [" + intervalo.getInicio()
					+ "," + intervalo.getFim() + "] e acabou em " + tempoEmNs
					+ " nanossegundos (" + (tempoEmNs / 1000000F)
					+ " milissegundos) e achou " + primosIntervalo.size()
					+ " primos!");
		}
	}

	public static List<Integer> buscaPrimos(int intervaloInicio,
			int intervaloFim, int numThreads) throws InterruptedException {
		intervalos = inicializaIntervalos(intervaloInicio, intervaloFim,
				2 * numThreads);
		
		List<PrimosParaleloSobDemanda> threads = inicializaThreads(numThreads);
		
		for (Thread thread : threads) {
			thread.start();
		}
		for (Thread thread : threads) {
			thread.join();
		}

		List<Integer> combinacao = new ArrayList<Integer>();
		for (PrimosParaleloSobDemanda primos : threads) {
			combinacao.addAll(primos.listaDePrimos);
		}
		return combinacao;
	}

	private static List<PrimosParaleloSobDemanda> inicializaThreads(
			int numThreads) {
		List<PrimosParaleloSobDemanda> threads = new ArrayList<PrimosParaleloSobDemanda>();
		for (int i = 0; i < numThreads; i++) {
			threads.add(new PrimosParaleloSobDemanda(i + 1));
		}
		return threads;
	}

	private static Queue<Intervalo> inicializaIntervalos(int inicio, int fim,
			int numIntervalos) {
		int blocos = ((fim - inicio) + 1) / numIntervalos;

		int inicioAux = inicio;
		int fimAux = inicioAux + blocos;

		Queue<Intervalo> intervalos = new LinkedList<Intervalo>();
		for (int i = 0; i < numIntervalos; i++) {
			if ((fimAux) > fim) {
				fimAux = fim;
			}

			intervalos.add(new Intervalo(inicioAux, fimAux));

			inicioAux = (fimAux + 1);
			fimAux = inicioAux + blocos;
		}

		return intervalos;
	}
}

class Intervalo {
	private int inicio;
	private int fim;
	
	public Intervalo(int inicio, int fim) {
		this.inicio = inicio;
		this.fim = fim;
	}

	public int getInicio() {
		return inicio;
	}

	public int getFim() {
		return fim;
	}
}